package l.l.w.CodingInterviews.滑动窗口的最大值;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created by llw on 2018/5/4/0004.
 */
public class 滑动窗口的最大值 {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(num == null || num.length == 0 || size > num.length) return result;
        LinkedList<Integer> windows = new LinkedList<Integer>();
        for(int i = 0; i < size; ++i){
            if(windows.isEmpty()){
                windows.add(i);
            }else{
                while(!windows.isEmpty() && num[i] > num[windows.getLast()]){
                    windows.removeLast();
                }
                windows.add(i);
            }
        }
        for(int i = size - 1; i < num.length; ++i){
            while(!windows.isEmpty() && i - size >= windows.getFirst()){
                windows.removeFirst();
            }
            while(!windows.isEmpty() && num[i] > num[windows.getLast()]){
                windows.removeLast();
            }
            windows.add(i);
            result.add(num[windows.getFirst()]);
        }
        return result;
    }
    public static void main(String[] args) {
        int[] num = {2,3,4,2,6,2,5,1};
        int size = 3;
        滑动窗口的最大值 solution = new 滑动窗口的最大值();
        ArrayList<Integer> result = solution.maxInWindows(num, size);
        System.out.println(result);
    }
}
